import java.util.ArrayList;
import java.util.Random;


public class GeneticAlgo {
    protected int populationSize;   // the population size
    protected double Pc;        // the probability of single point crossover 
    protected double Pm;        // the probability of bitwise mutation
    protected int bitsNum;              // the number of bits presenting a chromosome
    protected int generationsNum;   // the number of generations
    
    protected BitVector chromosome[];   //contains the population of chromosomes
    
    protected ArrayList<Integer> results;   // bests
    
    private int nodesCount;
    private static long initTime;
    
    // the constructor, sets all the genetic algorithm properties. 
    public GeneticAlgo(int populationSize, double Pc, double Pm, int bitsNum,int generationsNum){
        this.populationSize=populationSize;
        this.Pc=Pc;
        this.Pm=Pm;
        this.bitsNum=bitsNum;
        this.generationsNum=generationsNum;
    
        results=new ArrayList<Integer>();
    }

    /*Roulette Wheel selection - allows the best chromosomes to be repeatedly chosen to be in the new population */
    private BitVector[] selection(){
        //Pi=Fi/(sum of F)
        BitVector tmp[]=new BitVector[populationSize];
        double p[]=new double[populationSize];  // the probability of a chromosome to be chosen
        int sum=0;                              // the sum of all the chromosomes fitness
        for(int i=0;i<populationSize;i++)
            sum+=chromosome[i].getFitness();   // sum all the fitness
        
        for(int i=0;i<populationSize;i++){
            p[i]=(double)(chromosome[i].getFitness())/(double)sum;   // Pi=Fi/(sum of all fitness)
        }
        double rand = Math.random();
        ArrayList<BitVector> newPopulation = new ArrayList<BitVector>();
        int curSize;
        while (newPopulation.size() <= populationSize){
        curSize=newPopulation.size();
            for(int i=0;i<populationSize;i++){
                if (p[i]>rand)
                    newPopulation.add(chromosome[i]);
            }
            if (curSize == newPopulation.size())
                rand = Math.random();
        }
        for (int i=0;i<populationSize;++i)
            tmp[i]=newPopulation.get(i);
        return tmp; 
    }
    
    /*cross each adjacent couple of chromosomes that passes a random number probability at a random location*/ 
    private BitVector[] crossover() throws IllegalAccessException{
        Random r=new Random();
        BitVector tmp[]=new BitVector[populationSize];
        for(int i=0;i<populationSize;i+=2){ // for each pair of chromosoms  // ���� ���� ��� ��� �����
            if (i+1>=populationSize){
                tmp[i]=chromosome[i];
                return tmp;
            }
            if(Math.random()>Pc){           // then don't crossover
                tmp[i]=chromosome[i];
                tmp[i+1]=chromosome[i+1];
            }
            else{                           // then crossover
                BitVector crossed[]=BitVector.singlePointCrossOver(chromosome[i], chromosome[i+1],r.nextInt(bitsNum));
                tmp[i]=crossed[0];
                tmp[i+1]=crossed[1];
            }
        }
        return tmp;
    }

    /*For each bit of each chromosome if a random number between 0-1 is smaller than Pm switch the bit*/
    private BitVector[] mutation(){
        BitVector tmp[]=new BitVector[populationSize];
        for(int i=0;i<populationSize;i++){  // for each chromosom
            tmp[i]=chromosome[i];
            if(Math.random()<Pm){       // then mutate bit
               chromosome[i].mutateBit();
            }
        }
        return tmp;
    }
    
    /*runs the GA method*/
    public BitVector run() throws IllegalAccessException{
        BitVector bestResult=null;
        int val = 0;
        int nodesTillBest=0;
        initTime=System.currentTimeMillis();
        long timeTillBest=0;
        nodesCount=populationSize;
        chromosome=new BitVector[populationSize];
        for(int i=0;i<populationSize;i++){
            chromosome[i]=new BitVector(bitsNum);
        }
        for (int g = 0;val<AIUI.getMaxPossibleGrade() && g < generationsNum; ++g) {
            //calculate the Best value
            
            for (int i = 0;val<AIUI.getMaxPossibleGrade() &&  i < populationSize; ++i) {
                int fitness = chromosome[i].getFitness();
                if (fitness > val){
                    bestResult=chromosome[i];                    
                    val=fitness;
                    nodesTillBest=nodesCount;
                    long curTime=System.currentTimeMillis();
                    timeTillBest=curTime-initTime;
                }
                if (i%10 == 0){
                    AIUI.searchResults.addResults(val, bestResult, timeTillBest, nodesTillBest, false);
                }
            }
            if (val<AIUI.getMaxPossibleGrade()){
                chromosome = selection();
                chromosome = crossover();
                chromosome = mutation();
            }
            nodesCount+=populationSize;
        }
        AIUI.searchResults.addResults(val, bestResult, timeTillBest, nodesTillBest, false);
        return bestResult;
    }
    
    public ArrayList<Integer> getResults(){return results;}
}
